AtCoderBeginnerContest195 D問題400点 「Shipping Center」
https://gyazo.com/4e9f2a77f53da982fd4fb633e864597d
問題概要
制約
$ N, M, Q \leq 50
$ W_i, V_i, X_i \leq 10^6
解法・お気持ち
Greedyのリンクに証明動画があります(snukeさん).
解法としては,箱の容量が小さい順にソートします.
そして,小さい箱から「どれか1つの荷物を積むこと」を考えます.
このとき,積むべき荷物は「箱$ iに入る荷物の中で最も価値の高い荷物」を入れます.
これで,最適になります.
貪欲法は気持ちが大事なので,これで解けますがその簡易的な証明について考えます.
1. 荷物を入れることができるのに,あえて入れないという選択肢が最適である
https://gyazo.com/33e3f2d7d0f892da4902deb4a3a287ac
上のような状況を考えます.
ハコも荷物も容量順でソートされています.
ハコの図形の大きさは「容量」を,荷物の図形の大きさは「価値」を表します.
1つ目のハコに関して,入れることのできる荷物1, 2をスルーしあえて入れない状況が上の画像です.
ハコ2 ,3はそのとき入れることのできる最大の価値をそれぞれ選択しています.
このとき,ハコ1について,ハコ1が荷物1を選択し,ハコ2が荷物1を取ることをやめることを考えます.
これは,合計の価値は変化しないため,問題ありません.(価値が悪くなるようであれば,そのような操作は認められない)
https://gyazo.com/87fd9bae0575d9739259d754816545ad
よって,上の画像のように更新され,ハコ2をあとは荷物2に繋げばよくなります.
2. 入れることのできる荷物が複数あるとき,あえて価値の低い荷物を入れる
https://gyazo.com/880c60fe36acd7131c36835d7cafad7b
上のような画像の例を考えます.
ハコ1は荷物1, 2の両方を取れますが,あえて価値の低い荷物2を取っています.
そこで,これらをつなぎ替えることを考えます.
ハコ1は必ず荷物1を取ることができます.
なぜならば,自分より体が大きいハコ2が荷物1を選択しているため,当然荷物1を取得できます.
よって,交換が可能です.
これは,ハコの体積の昇順でソートを行っているためです.
よって,1,2より貪欲に価値の高い荷物を入れるということに操作をして持っていけるため,最適といえます.
計算量
$ O(NQ\log N)
新たな学び
貪欲法の証明のかんたんな理解
貪欲法をとっていて,途中で違う解法にかえる.それが最適と仮定するが,悪くならない操作を取ることによって貪欲法の状態に持っていく.
反省点
コード
code: cpp
int main() {
int N, M, Q;
cin >> N >> M >> Q;
vector<int> W(N), V(N);
REP(i, N) cin >> Wi >> Vi; vector<int> X(M);
cin >> X;
while (Q--) {
int L, R;
cin >> L >> R;
L--, R--;
vector<int> h;
for (int i = 0; i < M; i++) if (i < L or i > R) h.push_back(Xi); sort(h.begin(), h.end());
vector<bool> used(N);
int ans = 0;
for (auto x: h) {
PII p(-1, -1);
for (int i = 0; i < N; i++) {
chmax(p, make_pair(Vi, i)); }
if (p.second != -1) {
ans += p.first;
}
}
cout << ans << endl;
}
return 0;
}